package main

import "fmt"

//TreeNode 二叉树
type TreeNode struct {
	Data  string    //节点用来存放数据
	Left  *TreeNode //左子树
	Right *TreeNode //右子树
}

func NewTreeNode(str string) *TreeNode {
	return &TreeNode{Data: str}
}

//PreOrder 先序遍历
//先访问根节点 再访问左子树 最后访问右子树
func PreOrder(tree *TreeNode) {
	if tree == nil {
		return
	}
	//先打印根节点
	fmt.Print(tree.Data, " ")
	//再打印左节点
	PreOrder(tree.Left)
	//再打印右节点
	PreOrder(tree.Right)
}

//MidOrder 中序遍历
//先访问左子树 再访问根节点 最后访问右子树
func MidOrder(tree *TreeNode) {
	if tree == nil {
		return
	}

	//先打印左子树
	MidOrder(tree.Left)
	//再打印根节点
	fmt.Print(tree.Data, " ")
	//再打印右子树
	MidOrder(tree.Right)
}

//PostOrder 后序遍历
//先访问左子树 再访问右子树 最后访问根节点
func PostOrder(tree *TreeNode) {
	if tree == nil {
		return
	}

	//先打印左子树
	PostOrder(tree.Left)
	//再打印右子树
	PostOrder(tree.Right)
	//再打印根节点
	fmt.Print(tree.Data, " ")
}

func main() {
	t := NewTreeNode("A")
	t.Left = NewTreeNode("B")
	t.Right = NewTreeNode("C")
	t.Left.Left = NewTreeNode("D")
	t.Left.Right = NewTreeNode("E")
	t.Right.Left = NewTreeNode("F")
	/*树的形状
	       A
	    /     \
	   B       C
	  / \     /
	 D   E   F             */
	fmt.Println("先序排列：")
	PreOrder(t) //A B D E C F
	fmt.Println("\n中序排列：")
	MidOrder(t) //D B E A F C
	fmt.Println("\n后序排列：")
	PostOrder(t) //D E B F C A
}
